/**
 * @Date        : 2022/3/20
 * @Author      : sunxiangke(sunxiangke@baidu.com)
 * @Description :
 */

package main

import "fmt"

func main() {
	fmt.Println(sortedSquares([]int{-4, -2, -1, 1, 3}))
}

// 时间复杂度O(n)
func sortedSquares(nums []int) []int {
	n := len(nums)
	i, j, k := 0, n-1, n-1
	o := make([]int, n)
	for i <= j {
		is, js := nums[i]*nums[i], nums[j]*nums[j]
		if is > js {
			o[k] = is
			i++
		} else {
			o[k] = js
			j--
		}
		k--
	}

	return o
}
